package offer.day35;

public class No62LastRemaining {
    /*
     * 面试题62：圆圈中最后剩下的数字
     * 题目：0，1，2，......，n-1这n个数字排成一个圆圈，从数字0开始，
     * 每次从这个圆圈里删除第m个数字。	 * 求出这个圆圈里最后剩下的最后一个数字。
     * 例如：0，1，2，3，4这5个数字组成一个源泉，从数字0开始每次删除3个数字，
     * 则删除的前4个数字依次是2，0，4，1，因此最后剩下的数字是3
     *
     *
     * 思路：每次被删除的数字都有一定的规律  就可以直接计算出最后剩下的数字
     * 关系是：f(n) = 0                          当n = 0时
     * 		f(n) = [f(n-1,m)+m]%n	当n > 0时
     *
     * 也就是要想得到n个数字的序列中最后剩下的数字，
     * 就要得到n-1个数字的序列中最后剩下的数字，以此类推
     * 可使用循环或递归  循环更加简单易懂
     * */
    public static void main(String[] args) {
        No62LastRemaining n = new No62LastRemaining();
        System.out.println(n.LastRemaining(5, 3));
    }

    private int LastRemaining(int n, int m) {
        if(n<1||m<1) return -1;
        int last=0;
        for(int i=2;i<=n;i++){
            last = (last + m) % i;
        }
        return last;
    }
}
